Computer systems are often used to compose, store, retrieve, and update objects containing information. An application program such as a word processor or a spreadsheet is usually employed to perform these activities. Typically, a user composes an object by using an application program to input all of the contents of the object, using an input device such as a keyboard. As an example, if a user were to compose a report object containing several introductory paragraphs of text, a numerical table, and several conclusory paragraphs of text, the user would typically use a keyboard to type the introductory paragraph, the numerical table, and the conclusory paragraphs.
To facilitate the inputting of the contents of an object, a user may copy information from an existing object into the object being composed. This copying method has the advantage that it allows a user to avoid re-inputting information that has already been input. For example, when a user composes a report object and a ledger object already exists that contains the numerical table, the user may copy the numerical table from the ledger object into the report object instead of retyping the numerical table.
The copying method has the disadvantage that, when the numerical table is copied to the report object from the ledger object, the object loses its association with the ledger object. If the ledger object is then changed, the numerical table in the report object does not automatically change.
This loss of association disadvantage can be overcome by the use of object links. An object link (link) is a reference to a source object that is stored in a client object. The computer system treats the link as if the current contents of the source object are incorporated in the client object. When a user accesses the client object, the computer system encounters the link and then locates and accesses the source object. Locating the source object of a link is called resolving the link. When links are used, the current version of the source object is incorporated in the client object. The client object therefore has the benefit of any updates to the source object, even if they occurred after the link was created.
As an example of the use of links, a user can link a ledger object containing a numerical table of sales information into a report object containing a textual description of the sales information. FIG. 1 is a diagram illustrating the use of a link. A report object 101 named report.doc contains a link 102 to a ledger object 103 named ledger.xls. When the report.doc object is displayed, the link to the ledger.xls object is resolved, allowing the contents of the ledger.xls object to be accessed and incorporated in the display 104. Here, the ledger.xls object is the source object and the report.doc object is the client object.
Each link contains information used to locate where the source object is stored. Objects may be persistently stored in a variety of organizations on various storage devices. For example, a hierarchical file system stores objects as files. A hierarchical file system is a file system in which a root directory can contain files and subdirectories. Any subdirectory may contain files and further subdirectories. Thus, successive levels of subdirectories that descend from the root directory form a hierarchy. A pathname describes a location in the hierarchy, and each pathname refers to a file or subdirectory. For example, the pathname ".backslash.dos.backslash.copy.exe" describes a file named "copy.exe" contained in a directory called "dos", which in turn is contained in the root directory. Hierarchical file systems typically store links as pathnames.
Pathnames are either absolute or relative. An absolute pathname contains information needed to locate a file with respect to the root directory. A relative pathname, on the other hand, contains information necessary to locate a file with respect to the location of some other file. A link containing a relative pathname specifies the location of the source object relative to location of the client object. When a source object is located in the same directory as the client object, the link contains the source object name prefaced by the characters "..backslash.". Therefore, if the report.doc and ledger.xls objects were located in the same directory, the pathname in the link would be "..backslash.ledger.xls". An absolute pathname is an ordered list of the subdirectories into which one must successively descend to reach the source object, beginning with the root directory. If the ledger.xls object is in a directory named "acme", which in turn is in a directory called "companies" which in turn is in the root directory, the absolute pathname of the ledger.xls object is ".backslash.companies.backslash.acme.backslash.ledger.xls".
FIG. 2 shows a conventional method for storing and resolving links. Client object 200 is a report object. It contains a link to a ledger object, which in turn contains the absolute pathname of the source object, ".backslash.companies.backslash.acme.backslash.ledger.xls". As described above, this absolute pathname specifies a location in a file system hierarchy. The file system hierarchy contains directories 220-226. Directory 226 is the .backslash.companies.backslash.acme directory, which contains the source object. Directory 230 is a detailed view of directory 226. It contains a mapping of file names for files contained in the .backslash.companies.backslash.acme directory to file system identifiers. A file system identifier uniquely identifies a file in the file system. For example, directory 30 maps filename "report.doc" to file system identifier "&lt;fsid1&gt;" and filename "ledger.xls" to file system identifier "&lt;fsid2&gt;". A file system identifier table 240 then maps each file system identifier to an access information block. Each access information block contains a list of the locations and the storage media, or "sectors" that contain the data that comprise a file. For example, the file system identifier table maps from the file system identifier "&lt;fsid1&gt;" to access information block 250 and from file system identifier "&lt;fsid2&gt;" to access information block 260. Access information block 260 contains a list of the sectors that comprise the source file. Access information block 260 contains three references to comprise reference 263, reference 264, and reference 265. These references refer to sectors 273, 274, and 275 of the media 270, respectively.
Operating systems typically include commands that allow a user to move or rename an object. In a system supporting links between objects, the move or rename commands can be expanded to update the pathname in any link that refers to the moved or renamed object. However, operating systems also provide copy and delete commands that a user may use to move and rename objects. A user may rename an object by copying the object into the same directory and deleting the copied-from object. A user may move an object by copying the object into a different directory and deleting the copied-from object. Any time a user employs the copy and delete commands to move or rename a source object, any links to the source object may become impossible to resolve.
FIGS. 3A-3C are block diagrams that illustrate the problem that occurs when the copy and delete commands are used to rename a source object. In FIG. 3A, the report.doc object 301 contains a link 302 to the ledger.xls object 303. The link uses a relative pathname to refer to the ledger.xls object. If the link were resolved at this point, it would resolve correctly to the ledger.xls object. In FIG. 3B, the report.doc object, the ledger.xls object. and the link are unchanged. However the ledger.xls object has been copied to a growth.xls object 304. At this point, the link would still resolve to the ledger.xls object, because it still contains the pathname referring to the ledger.xls object. In FIG. 3C, the ledger.xls object has been deleted. Since the link still refers to the nonexistent ledger.xls object, the link cannot be resolved. At this point, a resolution of the link would fail, even though the growth.xls object is intended to be the renamed ledger.xls object. Any time a user employs the copy and delete commands to move or rename a source object, any links to the source object may become impossible to resolve.
Another situation in which links to source objects resolve incorrectly occurs when the object containing the link is moved to a different directory. FIGS. 4A-4B are block diagrams that illustrate the problem that occurs when the copy and delete commands are used to move a source object. FIG. 4A shows a report.doc object 401 containing a link 402 to a source ledger.xls object 403. The report.doc and ledger.xls objects are contained in a ".backslash.companies.backslash.acme" directory. A ".backslash.companies.backslash.ajax" directory contains a different but like-named ledger.xls object 404. While the report.doc object is in the ".backslash.companies.backslash.acme" directory, the link resolves correctly to the ledger.xls object 103. FIG. 4B shows the report.doc object moved to the ".backslash.companies.backslash.ajax" directory. When the report.doc object is in the ".backslash.companies.backslash.ajax" directory, the link resolves incorrectly to the ledger.xls object 404. A similar problem occurs when any object containing a link is moved such that the pathname stored in its link fails to describe any object or describes the wrong object.
In some computer systems that support linking, links each contain an object identifier instead of a pathname. A locator table is used to map the object identifier into a pathname. The level of indirection added by the locator table streamlines the process of updating the links to a source object that has been moved or renamed. No matter how many links to the source object exist, they can all be updated by merely changing the pathname once in the locator table. FIG. 5 is a block diagram that illustrates the implementation of a locator table. A locator table 501 contains object identifiers 511-514 which correspond to source object pathnames 521-524, respectively. Source objects 531-534 each contain a unique object identifier 541-544, respectively. Since the locator table contains entries for objects in many different directories, absolute pathnames are used. When a source object is linked to, its object identifier is copied into the link. The object with object identifier "1112" contains a link 551 to the object with object identifier "1111". If object 531, having object identifier "1111", was moved or renamed the link could be preserved by changing pathname 521 to correctly reflect the new name or location of object 531.
While the use of a locator table improves efficiency, it introduces a new problem with maintaining links. In order to prevent the loss of objects in cases of media failure or unintentional deletion, original objects are often copied from a primary storage device (e.g., a hard disk) to an archival storage device (e.g., a floppy disk). This copying is called archiving and the object produced by the copying is called an archived object. If any original object that has been archived is corrupted or erased, the corresponding archived object can be copied back to the primary storage device. This copying is called restoring the object, and the object produced by the copying is called a restored object. Restored objects usually replace the corrupted or deleted object on the primary storage device. However, because a user can move or change the name of an original object, restoring an object may result in having two copies of the same object on the primary storage device. Similarly, the user can specify to restore the object to a different directory, also resulting in having two copies of the same object on the primary storage device. Both copies share the same object identifier, but may have separate entries in the locator table. Since two entries may exist in the locator table for the same object identifier, the mapping from that object identifier to a pathname may be ambiguous. As a result, a link containing the duplicated object identifier may be resolved to either the original object or the restored object. Though the ambiguity is of little concern when the original object and the restored object are exact copies of one another, when either object is changed, it is essential that the correct object is chosen when resolving a link to their shared object identifier.
For example, if the object 531, having object identifier "1111", was archived from the ".backslash.companies.backslash.acme" directory, then restored to the ".backslash.companies.backslash.directory", a new entry (not shown) would be created in the locator table containing the object identifier "1111" and the pathname ".backslash.companies.backslash.ledger.xls". When the link in the 532 object is resolved, it may resolve to either the original object having the object identifier "1111" or the restored object having object identifier "1111", depending upon which of the corresponding locator table entries is encountered first when searching the table for an entry with object identifier "1111". If the objects remain exact copies, then it is unimportant which one the link resolves to. However, if the original object is edited to include more information, when the link resolves to the restored object, the information added by editing the original object would not be incorporated in the client object.
Source objects originally stored on a storage device of a computer system that is connected to one or more other computer systems by a network can easily be moved by a user to a storaae device of any other connected computer system. If a source object is not found by any of the above-described methods, it is common for the program searching for the source object to "broadcast" a request to each connected computer system to search for the source object on its storage devices and report back the results. While this "exhaustive search" approach is certain to effectively locate the source object if it is identifiable and stored on a storage device of a connected computer system, exhaustive searching is very expensive, in that it takes significant processing and storage retrieval resources for each connected computer system to search the full contents of each of its storage devices, and extensive network communications resources to broadcast the request and collect the results.